from typing import *


class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[[-1] * 4 for _ in range(n)] for _ in range(m)]
        d = [(-1, 1), (1, 1), (1, -1), (-1, -1)]

        def f(x, y, d):
            if who != -1 and dp[x][y][who][change] != -1:
                return dp[x][y][who][change]
            t = grid[x][y]
            for i in range(4):
                tx, ty = d[i][0] + x, d[i][1] + y
                if tx >= 0 and tx < m and ty >= 0 and ty < n and t ^ 2 == grid[tx][ty]:
                    if (i + 2) % 4 != who:
                        if i == who:
                            dp[x][y][who][change] = max(
                                dp[x][y][i][change], f(tx, ty, i, change) + 1
                            )
                        elif change > 0:
                            for k in range(4):
                                if (k + 2) % 4 != who:
                                    dp[x][y][who][change] = max(
                                        dp[x][y][who][change], f(tx, ty, k, 0) + 1
                                    )
            return dp[x][y][d

        for i in range(m):
            for j in range(n):
                if grid[i][j] != 1:
                    for k in range(4):
                        f(i, j, grid[i][j], 1)
        print(dp[1][3])


s = Solution()
print(
    s.lenOfVDiagonal(
        [
            [2, 2, 1, 2, 2],
            [2, 0, 2, 2, 0],
            [2, 0, 1, 1, 0],
            [1, 0, 2, 2, 2],
            [2, 0, 0, 2, 2],
        ]
    )
)
